/**
 * @Author Fizz Pu
 * @Date 2020/12/14 下午6:57
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 输入两个链表，找出它们的第一个公共节点。
 *
 * 如下面的两个链表：
 *
 *
 *
 * 在节点 c1 开始相交。
 */

// hashSet 空间复杂度O(1)

public class LeeOffer52 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
           int listALen = getLength(headA);
           int listBLen = getLength(headB);

           ListNode longer = (listALen > listBLen)  ? headA : headB;
           ListNode shorter = (listALen > listBLen) ? headB : headA;
           int moreStep = Math.abs(listALen - listBLen);

           for(int i = 0; i < moreStep; ++i){
               longer = longer.next;
           }

           while (longer != null && shorter != null &&  longer != shorter){
               longer = longer.next;
               shorter = shorter.next;
           }

           return longer;
    }


    private int getLength(ListNode head){
        int len = 0;
        ListNode node = head;

        while (node != null){
            ++len;
            node = node.next;
        }

        return len;
    }

}
